package algocasts;

public class P101_GetMiddleNode {
    class ListNode {
        int val;
        ListNode next;
    }

    public ListNode getMiddleNode_TwoPass(ListNode head) {
        ListNode p = head;
        int len = 0;
        for (; p != null; p = p.next) len++;
        p = head;
        for (int i = 0; i < len / 2; i++)
            p = p.next;
        return p;
    }

    public ListNode getMiddleNode_OnePass(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

}
